A. Field of the Invention
The present invention relates generally to data processing systems and, more particularly, to systems and methods for preserving the order of blocks of data processed by multiple processing paths in a data processing system.
B. Description of Related Art
In a data processing or communications system that must deliver high throughput in processing or communicating a stream of data, a conventional point-to-point approach is to provide n independent paths and distribute sub-streams of the data down each of the n paths. After processing by each of the n processing paths, the sub-streams are recombined to create an output stream. A problem that arises using this technique is that the different processing paths may have different delays. As a result, if a first block of data (e.g., a packet or cell) is sent down a first path at time t1 and a second block of data is sent down a second path at time t2>t1, the second block of data may nonetheless finish being processed before the first. Therefore, if nothing is done to correct for this differential delay, the recombined stream of data will be out-of-order relative to the input stream. Out-of-order blocks of data can be problematic in a number of data processing applications.
Out-of-order blocks of data are particularly difficult to prevent when there are R input streams, each connected to n processing paths, each of which is further connected to S output streams. In this “any-to-any” situation, different blocks of data from an input stream can be destined for different output streams. The blocks of data of each input stream are, thus, distributed across the processing paths and then concentrated back to the desired output stream. There are well-known algorithms for restoring order to mis-ordered streams at recombination time, based on attaching sequence numbers to consecutive blocks at input, and sorting blocks to restore consecutive sequence numbers on output. However, in the any-to-any application, a given output will not receive all sequence numbers from a given input, making the standard sorting algorithms impractical.
Therefore, there exists a need for systems and methods that preserve the order of blocks of data in data streams that have been distributed across multiple paths in a data processing system.